# -*- coding:utf-8 -*-

"""
题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
    @href https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:

    def __init__(self):
        self.res = []
        self.expectNumber = 0

    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        if root is None or root.val > expectNumber:
            return self.res

        self.expectNumber = expectNumber
        self.addList(root, 0, [])
        return self.res

    # 处理数据
    def addList(self, root, currentNumber, arr):

        number = root.val + currentNumber

        arr.append(root.val)
        # 相等时 增加到结果集中。
        if root.left is None and root.right is None:
            if number == self.expectNumber:
                self.res.append(arr)
                return

        # 处理左节点
        if root.left is not None and root.left.val + number <= self.expectNumber:
            self.addList(root.left, number, list(arr))

        # 处理右节点
        if root.right is not None and root.right.val + number <= self.expectNumber:
            self.addList(root.right, number, list(arr))


s = Solution()
r1 = TreeNode(10)
r1.right = TreeNode(12)
r1.left = TreeNode(5)
r1.left.left = TreeNode(4)
r1.left.right = TreeNode(7)
res = s.FindPath(r1, 22)
print(res)
